package com.gxc.array;

import java.util.HashSet;
import java.util.Set;

/**
 * 有一个由0和1组成的矩阵，每一行的左边是若干个连续的0，右边是若干个连续的1，返回1最多的行(数量一样就都返回)
 * 0000111
 * 0000000
 * 0000011
 * 0011111
 * 1111111
 * 0000000
 * 0011111
 */
public class LongestOne {

    public static void main(String[] args) {
        int[][] array = random();

        
        Set<Integer> set = longestOne(array);
        for (Integer integer : set) {
            System.out.println(integer);
        }
        System.out.println("--------------");
        set = process(array);
        for (Integer integer : set) {
            System.out.println(integer);
        }


        System.out.println("***************");
        array = random2();
        set = longestOne(array);
        for (Integer integer : set) {
            System.out.println(integer);
        }
        System.out.println("--------------");
        set = process(array);
        for (Integer integer : set) {
            System.out.println(integer);
        }
    }

    /**
     * 从右上角开始
     * 如果当前位置是1，则向左移动，直到遇到0，当前长度就是该行最长的1的长度
     * 如果当前位置是0，则向下移动,统计该行1的长度
     * @param array
     * @return
     */
    public static Set<Integer> longestOne(int[][] array) {
        if (array ==null || array.length ==0) return null;
        Set<Integer> set = new HashSet<>();

        int maxCol = array[0].length-1;
        int row = 0;
        int col = maxCol;
        //1的连续最大值
        int max = Integer.MIN_VALUE;
        while (row<array.length) {
            if (array[row][col] == 1) {
                if (col>0) col--;
                else {
                    //col == 0  该行从第一列开始都是1，则添加至集合
                    if (maxCol-col > max) {
                        max = maxCol-col;
                        set.clear();
                        set.add(row);
                        //如果该行的1的长度与最大长度相等，则也添加至集合
                    } else if (col+1 <= maxCol && array[row][col+1] == 1) {
                        set.add(row);
                    }
                    row++;
                }
            } else {
                //统计该行1的长度,如果大于历史最大长度，则更新
                if (maxCol-col > max) {
                    max = maxCol-col;
                    set.clear();
                    set.add(row);
                    //如果该行的1的长度与最大长度相等，则也添加至集合
                } else if (col+1 <= maxCol && array[row][col+1] == 1) {
                    set.add(row);
                }
                row++;
            }
        }

        return set;
    }

    public static Set<Integer> process(int[][] array) {
        if (array ==null || array.length ==0) return null;
        Set<Integer> set = new HashSet<>();

        int maxCol = array[0].length-1;
        int row = 0;
        int col = maxCol;
        int max = 0;
        //1的连续最大值
        while (row<array.length) {
            //如果当前位置是0，则向下移动
            if (array[row][col] == 0) {
                if (col+1 <= maxCol && array[row][col+1] == 1) {
                    set.add(row);
                }
                row++;
            } else {
                //历史的连续1的长度
                int temp = max;
                //本行的连续1长度
                while (col>=1 && array[row][col]==1){
                    col--;
                    max++;
                }
                //本行的连续1长度 > 历史的连续1的长度
                if (max>temp) {
                    set.clear();
                }
                set.add(row);
                row++;
            }
        }
        return set;
    }

    /**
     *  * 0000111
     *  * 0000000
     *  * 0000011
     *  * 0011111
     *  * 1111111
     *  * 0000000
     *  * 0011111
     * @return
     */
    private static int[][] random() {
        int[][] array = new int[7][7];
        array[0][4] = 1;
        array[0][5] = 1;
        array[0][6] = 1;

        array[2][5] = 1;
        array[2][6] = 1;

        array[3][2] = 1;
        array[3][3] = 1;
        array[3][4] = 1;
        array[3][5] = 1;
        array[3][6] = 1;

        array[4][0] = 1;
        array[4][1] = 1;
        array[4][2] = 1;
        array[4][3] = 1;
        array[4][4] = 1;
        array[4][5] = 1;
        array[4][6] = 1;

        array[6][2] = 1;
        array[6][3] = 1;
        array[6][4] = 1;
        array[6][5] = 1;
        array[6][6] = 1;

        return array;
    }

    /**
     *  * 0000111
     *  * 0000000
     *  * 0000011
     *  * 0011111
     *  * 0111111
     *  * 0000000
     *  * 0111111
     * @return
     */
    private static int[][] random2() {
        int[][] array = new int[7][7];
        array[0][4] = 1;
        array[0][5] = 1;
        array[0][6] = 1;

        array[2][5] = 1;
        array[2][6] = 1;

        array[3][2] = 1;
        array[3][3] = 1;
        array[3][4] = 1;
        array[3][5] = 1;
        array[3][6] = 1;

        array[4][1] = 1;
        array[4][2] = 1;
        array[4][3] = 1;
        array[4][4] = 1;
        array[4][5] = 1;
        array[4][6] = 1;

        array[6][1] = 1;
        array[6][2] = 1;
        array[6][3] = 1;
        array[6][4] = 1;
        array[6][5] = 1;
        array[6][6] = 1;

        return array;
    }
}
